from typing import List


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 基于单调栈构建nums2数组对应的下一个更大元素下表数组next_gt
        stack = [] # 栈顶最小，找到下一个最大的数后出栈
        next_gt = [-1] * len(nums2)
        for idx in range(0, len(nums2)):
            while stack and nums2[idx] > nums2[stack[-1]]:
                next_gt[stack.pop()] = idx
            stack.append(idx)
        while stack:
            next_gt[stack.pop()] = -1
        # print(next_gt)

        # 获取nums1元素对应在nums2中的下一个更大元素
        ret = [-1] * len(nums1)
        for idx_1, value in enumerate(nums1):
            idx_2 = nums2.index(value)
            if next_gt[idx_2] != -1:
                ret[idx_1] = nums2[next_gt[idx_2]]
        return ret